<html>
<head><meta charset="utf-8"><title>Range::binary_search · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html">Range::binary_search</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="185397936"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185397936" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Tim Vermeulen <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185397936">(Jan 11 2020 at 17:23)</a>:</h4>
<p>I've long wanted to add a binary search to <code>Range</code> because of how useful binary search can be even without a slice, how could this best be approached?<br>
It doesn't seem possible to use the <code>Step</code> trait in its current form for this, so I see a couple options:</p>
<ul>
<li>modify the <code>Step</code> trait</li>
<li>add a new trait</li>
<li>use a macro to implement it for all integer types</li>
<li>only implement it for <code>Range&lt;usize&gt;</code> (since that's by far the most important one)<br>
None of these seem great, I'm leaning towards the last option because it leaves all other options open, but I'm hoping there's another option I haven't thought of.</li>
</ul>



<a name="185398141"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185398141" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185398141">(Jan 11 2020 at 17:28)</a>:</h4>
<p>What do you mean by binary search on range? What would you be searching <em>in</em>?</p>



<a name="185398482"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185398482" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Tim Vermeulen <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185398482">(Jan 11 2020 at 17:39)</a>:</h4>
<p>You'd be searching in the range itself. I should have been more specific, this only works with <code>binary_search_by</code> and <code>binary_search_by_key</code>, <code>binary_search</code> as it's currently on <code>[T]</code> would indeed make no sense</p>



<a name="185398597"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185398597" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Tim Vermeulen <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185398597">(Jan 11 2020 at 17:42)</a>:</h4>
<p>The signature of <code>Range&lt;usize&gt;::binary_search_by</code> would be</p>
<div class="codehilite"><pre><span></span><span class="k">fn</span> <span class="nf">binary_search_by</span><span class="o">&lt;</span><span class="n">F</span>: <span class="nb">FnMut</span><span class="p">(</span><span class="kt">usize</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nc">Ordering</span><span class="o">&gt;</span><span class="p">(</span><span class="o">&amp;</span><span class="bp">self</span><span class="p">,</span><span class="w"> </span><span class="n">f</span>: <span class="nc">F</span><span class="p">)</span><span class="w"> </span>-&gt; <span class="nb">Result</span><span class="o">&lt;</span><span class="kt">usize</span><span class="p">,</span><span class="w"> </span><span class="kt">usize</span><span class="o">&gt;</span><span class="w"></span>
</pre></div>


<p>and using that <code>[T]::binary_search_by</code> could be reimplemented using something like <code>(0..self.len()).binary_search_by(|i| f(self[i]))</code></p>



<a name="185398810"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185398810" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> kennytm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185398810">(Jan 11 2020 at 17:49)</a>:</h4>
<p>is it something like Go's <a href="https://godoc.org/sort#Search" target="_blank" title="https://godoc.org/sort#Search"><code>sort.Search</code></a>?</p>



<a name="185399054"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/Range%3A%3Abinary_search/near/185399054" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Tim Vermeulen <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/Range.3A.3Abinary_search.html#185399054">(Jan 11 2020 at 17:56)</a>:</h4>
<p>It does seem like it! The main difference being that by having the closure return an <code>Ordering</code>, the function is able to return <code>Ok</code>/<code>Err</code> depending on whether the search "succeeded"</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>